In a digital color imaging system, a color image is represented as a set of color picture elements ("pixels"). Each pixel has associated with it a set of color values which describe the color (hue, saturation and lightness) for that position in the image. The color values correspond to the color coordinates in some given color space. There are many different color spaces (e.g. RGB, CIE tristimulus (XYZ), CIELAB, CIELUV, CMY(K), etc.) which are commonly used. Some color spaces, such as XYZ, CIELAB, and CIELUV are device independent and will therefore give an absolute measure of the color for each pixel in the image. Others, such as RGB and CMY(K), are device dependent and can only be related to an absolute color value if the spectral characteristics of a specific device are known.
For many applications it may be necessary to be able to take color image data from one device and display, manipulate, and/or print it on another device which may have very different spectral characteristics. For this reason, it is often necessary to be able to take image data in one color space, and convert it to a different color space. For example, it may be required to take RGB data from an input scanner and convert it to a device independent space such as CIELAB. This device independent data could then be used by a variety of different output devices which could then convert the data to their own device dependent color space for display. This permits the various devices to be calibrated so that the image will have the same color appearance regardless of what output device is used.
The transformation from one color system to another relates the coordinates in one space to those in a different color space. In some cases, this color transformation may be as simple as a matrix multiplication, as in the case of transforming from a video RGB space to XYZ. In other cases the transformation is more complex, such as when transforming CIELAB into CMY(K).
A technique which is used in many applications to implement various color space transformations is a multi-dimensional color-calibration look-up table. This approach has the advantage over other methods, such as matrix techniques, that very general color transformations can be specified. This is particularly helpful for transforming to hard-copy device color spaces due to their complex color reproduction characteristics. Due to the flexibility of the multi-dimensional look-up table approach, it is also useful for implementing many color enhancement schemes, and for combining many color transformation steps into a single step. This approach can be implemented in digital hardware and permits fast "computation" of the color transformation even when the actual mathematical equations relating the two color spaces are very complex.
The basis of the multi-dimensional look-up table approach is to store the output color values for a large number of combinations of input color values. For example, to convert from a video RGB space to a printer CMY(K) space, the desired printer code values could be stored for every combination of input RGB values. However, if each channel of the input RGB space consisted of 8-bit numbers, this would require storing 256.sup.3 =16,777,216 different output color values. For an 8-bit CMYK printer 64 MBytes of memory would be required to store the table. This would be impractical for many applications due to the large memory requirements. In practice, it is usually necessary to use smaller look-up tables. For example, reducing the table size to 16.sup.3 will reduce the required memory in the above example to 16 KBytes. One way to use this smaller table is simply to quantize the input color values to the nearest look-up table entry. This configuration is shown in FIG. 1., where in a generalized environment input color image data exists in some multi-channel color space, denoted as ABC, where ABC may represent RGB, XYZ, CIELAB, CIELUV, CMY(K), etc. The color coordinates in this space are known with some precision specified by the number of digital levels, N.sub.o. It is desired to convert the color information for some image into another color space, denoted as DEF, with some precision specified by the number of digital levels in the output color space (N.sub.c levels). The color conversion is carried out using a group of quantizers 10 which quantize the input color signals A.sub.o, B.sub.o, and C.sub.o to N.sub.q levels providing the quantized color signals A.sub. q, B.sub.q, and C.sub.q, which are used to address a multi-dimensional color-calibration look-up table 12. The number of dimensions for the look-up table 12 corresponds to the number of color parameters in the input color space. Usually this is three dimensions, with the exception of CMYK space which would have four dimensions. In general, the number of digital levels for each channel of the input color space may be different, e.g., channel B may have N.sub.qB =64 levels and channels A and C may have N.sub.qA,C =32 levels. The color-calibration table 12 contains pre-calculated output color values for every possible combination of quantized input color values.
The problem that arises in using the approach shown in FIG. 1 is that many input colors are mapped to a single output color. The result will be image artifacts such as contouring where a smooth gradient in the input color space gets mapped to a stair-step in the output color space. The visibility of these artifacts can be minimized by choosing the optimum quantization levels to store in the look-up table as taught by Spaulding, Ray and Sullivan (U.S. patent application Ser. No. 980,860 filed Nov. 24, 1992). Although this will minimize the visibility of the quantization artifacts, it can not eliminate them altogether when small look-up table sizes are used.
Another method which is sometimes used to eliminate the quantization artifacts associated with small color-calibration look-up table sizes is to use an interpolation algorithm to approximate the output color values for input colors which are intermediate to the values that are stored in the table. A variety of interpolation methods can be used including tri-linear interpolation, and tetrahedral interpolation. Although this approach can effectively eliminate many of the artifacts introduced by the small look-up table size, the amount of extra computation associated with the interpolation will have a negative impact on the implementation speed.
Another approach, to minimizing the appearance of artifacts without adding the extra computation associated with interpolation is shown in U.S. Pat. No. 5,162,925 issued Nov. 10, 1992 to Takaoka et al. Takaoka et al disclose the use of a form of error diffusion on the input color signal to distribute truncation (a form of linear quantization) errors over a neighborhood of pixels in a processed image. This approach is shown in FIG. 2, where an 8 bit input signal is supplied to a latch circuit 14, which latches the lower order 2 bits of the picture element data, that is the input color image signals. The latched data is multiplied by a set of weighting coefficients 1 to 1+n in a set of multipliers 15-0 to 15-n and delayed by a set of FIFO (FIRST IN FIRST OUT) circuits 16-0 to 16-n. The delayed outputs of the FIFO circuits are added to the input color signal associated with neighboring picture elements in an adder 17. The modified input signal is applied to a shift circuit 18 to provide a form of linear quantization. A shortcoming with this process is that the local mean of the input signal is not generally preserved in the quantized output signal. Since the local mean of the input signal is not preserved in the quantized output signal, the quantized output signal still displays contouring artifacts.